COMMENT ⊗   VALID 00004 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002		Part one: Functions as passive objects
C00009 00003		Part two: Functions as active objects
C00011 00004	     The Art of Computer Science: Undergraduate Special Topics Course
C00016 ENDMK
C⊗;
	Part one: Functions as passive objects

1  Notation
 	The role of notation in science
	 expressivity
	 subordination of detail
	 economy
	 amenability to proof
	The impact of computing on notation
	 executability
	 representability of algorithms
	The difficulties with programming languages

  Computation and interaction
	The relationship between language and its medium
	 why computing languages cannot be separated
	   from the programming env
	 cf. conversation and understanding
	The polarization between interaction and discipline
	 pascal vs. lisp  vs. ucsd pascal  vs smalltalk
	The polarization between rigor and hacking
	 basic vs. (lisp/scheme)

lab: use wordsmith to create  simple text files


2  The language
3	Data domain: The whole numbers
	Algorithmic notation
	 conditional expressions
	 definitions
	   recursion
	 numerical examples
	computation as deduction
	   axioms for number theroy
	   rules of inference
	     substitution and simplification
		number theory
		conditional
	   the concept of proof
	    equivalence
	    termination
	Data Domain: symbolic expressions
	 the representability of programs
 	 abstract objects
	 constructors, selectors, and recognizers
	The mapping of expressions to data structures
	Non-numeric computation: examples
	  evaluation of polynomials
	  simplification of algebraic expressions
	  propositional logic: evaluation
	    ?theorem proving
	  binary trees (l-n-r) rep, sort, add, del
	  missionaries and cannibal
 	  game stuff

4  Evaluation
5	Deduction vs computation, again
	 systems for substitution and simplification
	 computation as controlled deduction
	 call-by-name vs. call-by-value
	Semantics of programming languages
	Representability of programs
	 a detailed discussion
	An evaluation algorithm
	 The operational view
	Implementation strategies
	 call-by-value
	 weak vs. strong conditional
	 simulation of substitution
	extending the evaluator
	 macros and read-macros: abbreviational convenience
	 iteration: language extension and special forms
	

6  A modern LISP: more data structuring
7	The idea of "first-class data"
	implementation-driven languages violate notational principles
	 arbitrary precision numbers
 	 Strings
	 Arrays
	 property-lists (flex records)

8  Property-lists and message passing
	classes as properties
	algorithms as message passing
	hieracharies and flavors
	  hierarchies as implementation simplification

9  Object-oriented programming
10	Smalltalk and Actors

11 Lexical vs dynamic scoping: the beginnings of active functions
	Evaluation revisited
	 functionals
	 the difficulty with functional arguments
	 variables: local, free, global
	 added complexity of functional values

6  Control: function vs algorithm
	an analysis of the evaluator
	 the run-time structure
	   stacks
	   stacks+access and control links
	   tree access, control stack
	   tree access, tree control

7  Applicative v.s. imperative
	control as a programming tool
	 side-effects
	  assignment, rplaca, rplacd

13 Implementation considerations
	implementation of the evaluation process
	 read
	  parsers and scanners
	   searching and hashing
	 print
	runtime language support
 	 i-j pairs
	 shallow versus deep
	run-time data support
	 numbers
	 arbitrary precision numbers
	 trees
	  programmer maintained
	  reference counting
	  garbage collection
	   mark sweep
	   copy-compacting
	    cheney
	    baker
	    henry&carl

12 Machines and compiling
13	The LISP machine
	Traditional machines as microcode
	Compilation
	 program representation
	  list structure
	  scheme hacks
	  p-code/byte code/MACRO
	  machine specific
	Hardware
	  LISP machine
	  Scheme chips

14 The Racks paper: a bridge  from passive to active
	Part two: Functions as active objects

14 Functions as first-class objects
15	Relationship between 
	  purity:lexical and
	  utility: dynamic
	interactive creation of functional objects
	 programming in "levels"

		
16 Applications of functional objects
     car,cdr, cons as:
	1. arrays and functional
	2. pure functional  (t, f)
	3. 1 as msg passing
17   stacks as functionals (gls/gjs)
18   multiprocessing (wand/aip)

19 Evaluation of Functionals
	evaluators for full funarg 
	evaluators for smalltalk (ingalls)

20 Applications of lisp-related computing
	cad
	nl
	business data bases  --must do much better here

21 The future of computing
	interactive programming
	language designs
	theory
	ai applications
     The Art of Computer Science: Undergraduate Special Topics Course

The point  of  the  course  is  to  present  the  fundamental  notions  of
computing.

The course has the same general  characteristic as that of the  functional
programming  class,  but  will  use  a  curriculum  based  on  access   to
interactive personal computers  as the  primary tool  for gaining  fluency
with the concepts and gaining an understanding of interactive computing.

The notions of computing are  quite simple, yet the contemporary  approach
tends to obfuscate rather than  illuminate.  At the concept level,  simple
ideas become buried in syntax:   algorithms are confused with  programming
language syntax;  computation is  confused  with compiling;  compiling  is
confused with syntax analysis.

On the technological side, the Practice of computing suffers from the dead
weight of twenty years of batch processing.  "Glass teletypes" create card
decks and text  editors manipulate card  images.  Alas, certain  computing
"methodologies"  even  glory  in  the  "discipline"  that  such  primitive
interaction forces one to endure.


Without an understanding  of fundamental  concepts, and  saddled with  the
outdated and  stilted programming  techniques, it  is not  suprising  that
computer-related productivity is falling.


Fortunately, the intellectual legacy of mathematical logic and be  coupled
with a few insights of modern  computing to supply an adequate  foundation
for modern computing.  The missing  ingredient in the traditional  setting
was the baroque computing engine that logicians used; a Turing machine  is
a dreadful  architecture.   The fundamentals  of  the new  formalism  were
discussed by John McCarthy  twenty years ago, and  have been the basis  of
the programming language named LISP. The new ingredient is the development
of the personal computing environment.  One cannot effectively learn about
computing without practicing  the art. Until  recently, appropriate  tools
for computing "practice" have  been restricted to research  establishments
for at  least two  reasons.   First, many  of  the ideas  about  effective
interactive environments have been the subject of research; secondly,  and
more immediate, the cost of these components has been extraordinally high.
Technology has changed that second  consideration, and the research  ideas
have reached a  synthesis stage. The  time is therefore  ripe to move  the
intellectual  and  methodological  and  technological  results  into   the
educational domain.  That is the intent of this course.